package com.jorenwu.asymmetric;

import java.util.Random;

public class PohligHellmanFactorization implements Factorization
{
	private long p, q, e, g, u;

	public PohligHellmanFactorization(long p, long e, long g, long u)
	{
		this.g = g;
		this.p = p;
		this.q = p - 1;
		this.e = e;
		this.u = u;
	}

	public long factorize()
	{
		return phFactorization(p, q, e, g, u);
	}

	private long phFactorization(long p, long q, long e, long g, long u)
	{
		long s, r, y;
		if (e == 1)
			return new ShanksFactorization(p, g, u).factorize();
		else
		{
			Random rn = new Random(e);
			s = rn.nextLong();
			r = phFactorization(p, q, s,(long) Math.pow(g, Math.pow(q, e - s)), (long) Math.pow(u,
							Math.pow(q, e - s)));
			y = phFactorization(p, q, e - s,
					(long) Math.pow(g, Math.pow(q, s)), u
							/ (long) Math.pow(g, r));
		}
		return y * (long) Math.pow(q, s) + r;
	}

}
